분기 예측

Branch Prediction

1. 개요2. 종류

2.1. 정적 분기 예측2.2. 동적 분기 예측

2.2.1. 분기 예측 버퍼2.2.2. 연관 분기 예측

3. 관련 문서

1. 개요 [편집]

파이프라인이 등장하면서 CPU는 수행이 채 끝나지도 않은 명령어의 결과를 사용해야 하는 일이 종종 있게 되었다. 특히 분기 명령어(branch instruction)의 경우 그 조건을 평가하는 데 필요한 값이 아직 계산되고 있다면, 어떤 명령어를 다음에 수행해야 할지 명령어를 가져오는(fetch) 단계에서 아직 판단할 수 없으므로 필요한 값이 다 계산될 때까지 기다리는(stall) 수밖에 없었는데, 이는 CPU의 성능을 크게 떨어뜨리는 요인이 되었다. 특히 이는 파이프라인이 깊어지면서 더 심해지는 문제였다. 그래서 필요한 값을 기다리지 않고 어떻게 분기할지 예측하여 파이프라인이 끊기지 않고 계속 수행되도록 하는 기법들이 여럿 등장하게 되었다. 이에 따라 CPU는 명령어를 가져오는 단계에서 분기 명령어의 조건을 아직 평가할 수 없다면 어떻게 분기할지 예측하여 그대로 다음 명령어를 수행하고, 나중에 조건을 평가할 수 있을 때 앞서의 예측이 틀렸다면 예측하여 수행된 명령어들을 취소하고 올바른 분기의 명령어를 다시 수행하게 된다. 다만 주의할 점은 이런 식의 추측 실행(speculative execution)을 할 경우에 명령어들은 취소되었지만 명령어가 참조한 메모리가 캐시에 올라오는 등 부작용(side effect)은 여전히 남아 있을 수 있는데, 프로세서 설계 시 이를 간과했다가 터진 것이 CPU게이트.

높은 정확성의 분기 예측이 가능한 것은 프로그램 안에 있는 각 분기 명령어가 대부분 분기되거나(taken) 분기되지 않거나(not taken)의 둘 중 한 쪽 경우를 훨씬 많이 이용하는 경향성이 있기 때문이다. 예컨대 분기 명령어 하나로만 구성된 간단한 do-while 루프를 생각해 보자. 보통 루프를 계속 수행하는 경우가 루프를 벗어나는 경우보다 훨씬 많으므로, 돌아가는 분기를 타는(taken) 쪽으로 예측하면 정확성이 높을 것이다.

2. 종류 [편집]

2.1. 정적 분기 예측 [편집]

Static Branch Prediction

가장 간단한 방식으로, 실행시간 정보에 의존하지 않고 분기 예측을 수행한다. 이 중에서 유명한 것으로 BTFNT(Backward taken, Forward not taken)가 있는데, 이는 말 그대로 분기의 방향이 순방향이면 분기를 타지 않고, 역방향이면 분기를 타는 방식이다. 이는 루프의 수행 방식에서 착상한 것으로, 루프에서는 계속 수행하는 경우가 더 많은데 이는 역방향 분기의 경우이므로 분기를 타는 경우로 예측하고, break 문과 같이 루프를 벗어나서 다음 흐름을 실행하는 분기는 루프가 계속 수행되는 도중에는 잘 일어나지 않는데 이는 순방향 분기의 경우이므로 분기를 타지 않는 경우로 예측하는 것이다.

2.2. 동적 분기 예측 [편집]

Dynamic Branch Prediction

실행시간 정보를 활용하여 분기 예측을 수행한다. 보통 정적 분기 예측보다 정확도가 더 높다.

2.2.1. 분기 예측 버퍼 [편집]

Branch Prediction Buffer

각 분기 명령어마다 지난번에 그 분기가 실행되었는지의 여부를 저장해서 지난번에 분기되었다면 이번에도 분기하는 것으로, 아니라면 이번에도 아닌 것으로 예측해 보자. 그러면 각 분기 명령어는 분기하는 경우와 아닌 경우 둘 중 하나를 훨씬 많이 이용하므로, 대부분의 경우에는 지난번에 수행된 결과와 이번에 수행될 결과가 같을 것이다. 이렇게 각 분기당 1-bit의 버퍼만 사용하여 예측을 할 수있다. 물론 CPU 내부에 들어갈 수 있는 메모리는 한정적이므로 실제로는 모든 분기 명령어에 대해 bit를 할당하기보다는 직접사상 캐시(direct mapped cache)처럼 분기 명령어 주소의 낮은 쪽 bit들을 버퍼 칸 번호로 이용하여 다대일 사상이 되도록 할 것이다. 이런 방식에는 문제점이 하나 있는데, 만약 분기 예측이 한 번 틀렸다면 그것은 그 분기의 경향성과 다르지만 어쨌든 이번에 수행된 결과가 버퍼에 저장되므로 다음에도 또 틀릴 가능성이 높다는 것이다. 이런 문제를 해결하기 위해 버퍼당 2bit를 사용하여 두 번 연속으로 틀렸을 때만 예측을 바꾸도록 하면 더 좋은 성능을 낼 수 있다. 한 분기 당 3bit 이상을 사용하는 것은 성능을 아주 조금만 증가시킬 뿐이다.

2.2.2. 연관 분기 예측 [편집]

Correlating Branch Prediction

바로 앞에서 설명한 간단한 분기 예측 버퍼는 각각의 분기 명령어의 수행 결과를 예측할 때 그 명령어 하나의 이전 수행 결과만 사용한다. 어떤 분기 명령어의 실행은 분명 다른 분기 명령어의 수행에 의존하므로, 다른 분기 명령어(특히 최근에 수행된 것들)의 수행 결과까지 사용한다면 더 높은 예측의 정확성을 얻을 수 있을 것이다. 이제 최근에 수행된 분기 명령어의 결과 m 개를 기록해 두고, 각각의 결과를 조합한 2^m개의 경우마다 위의 n-bit 예측 버퍼 하나씩을 사용한 것을 (m, n) 예측기라고 하자. 만약 버퍼 칸 수가 E개라면 (m, n) 예측기에 필요한 버퍼의 총 크기는 버퍼 자체의 크기인 n bit * 2^m * E + 최근 수행된 결과를 기록할 m bit가 된다.